
import java.util.Iterator;
import java.util.Scanner;


/**
 *
 * @author Valdez
 */
public class HuffmanDriver {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        
        //variables
        Scanner s = new Scanner(System.in).useDelimiter("");
        List freq = new SinglyLinkedList();
        PriorityVector trees = new PriorityVector();
        
        //leer lo que escribe el usuario
        while (s.hasNext()) {
            char c = s.next().charAt(0);
            if (c == '\n') break;
            NodeHuffman query = new NodeHuffman(c);
            NodeHuffman item = (NodeHuffman)freq.remove(query);
            if (item == null) {        
                freq.addFirst(query);
            } else {                 
                item.frequency++;
                freq.addFirst(item);
            }
        }
        
        
        Iterator it = freq.iterator();
        while (it.hasNext()) {
            trees.add(new HuffmanTree((NodeHuffman)it.next()));
        }
        
        //inserta caracter en un arbol de Huffman
        while (trees.size() > 1) {
            // obtiene los dos arboles de menor frecuencia
            HuffmanTree smallest = (HuffmanTree)trees.remove();
            HuffmanTree small = (HuffmanTree)trees.remove();
            // agrega un arbol conteniendo los dos
            trees.add(new HuffmanTree(smallest,small));
        }
        
        HuffmanTree encoding = (HuffmanTree)trees.remove();
        encoding.print();
    }
}
